1. Field of the Invention
The present invention relates to computer arithmetic circuits and operating methods. More specifically, the invention relates to a two-bit Booth multiplier circuit.
2. Description of the Related Art
FIG. 1, which is labeled prior art, illustrates a block diagram of a simple Booth multiplier 100 for signed integers. The numbers x=x.sub.n-1 x.sub.n-2. . . x.sub.0 and y=y.sub.n-1 Y.sub.n-2. . . y.sub.0 are respectively placed into register X 102 and register Y 104 for multiplication by the Booth multiplier 100 and a register P 106 is initially set to zero. A multiplication operation is executed in a sequence of two-part iterations. In a first part, register Y 104 containing bits Y.sub.n-1 y.sub.n-2. . . y.sub.0 is added to register P 106 when the least significant bit of register X 102 is 1. Register P 106 is left unchanged when the least significant bit of register X 102 is 0. In a second part, register P 106 and register X 102 are shifted right with the low-order bit of register P 106 moving to the high-order bit of register X 102 and the low-order bit of register X 102 discarded. After n iterations, the multiplication product is held in register P 106 and register X 102 with the least-significant bits held in register X 102.
Booth recoding in a Booth multiplier circuit is useful for implementing a multiplication operation that operates on both on unsigned and signed numbers. For unsigned multiplication, the unsigned numbers are converted to signed numbers by appending a zero value bit to the left of the most significant bit (x.sub.n-1) of a number x=X.sub.n-1 x.sub.n-2. . . x.sub.0. Accordingly, a set of rules are defined for implementing a Booth multiplier 100 assuming that register X 102 initially holds a number x=x.sub.n-1 x.sub.n-2. . . x.sub.0 and a zero value bit is appended to the right of the least significant bit (x.sub.0) of the number x=x.sub.n-1 x.sub.n-2. . . x.sub.0 for a Booth encoding. The rules applied to the Booth multiplier where x.sub.i-1 is initially 0 and the ith multiply iteration the low-order bit of register X 102 is x.sub.i, are as follows:
(1) If x.sub.i =0 and x.sub.i-1 =0, then add 0 to register P 106. PA1 (2) If x.sub.i =0 and x.sub.i-1 =1, then add register Y 104 to register P 106. PA1 (3) If x.sub.1 =1 and x.sub.i-1 =0, then subtract register Y 104 from register P 106. PA1 (4) If x.sub.i =1 and x.sub.i-1 =1, then add 0 to register P 106.
A simple technique for implementing the rules for the Booth multiplier 100 involves extending the register X 102 one bit to the right to define a new bit x.sub.-1. Two's complement multiplication is implemented by taking into consideration the sign of the value in register P 106 while the register P 106 is shifted right and saving the most recently shifted bit of register X 102 for usage in deciding whether to add or subtract register Y 104 from register P 106.
Various considerations are taken into account in the design of a multiplier circuit. For example, if operating speed is paramount, a multiplier circuit typically includes a plurality of adders forming a multiplier array. A full-range multiplier array generally includes an adder for each of the bits in a multiplicand. Unfortunately, a multiplier circuit having a plurality of adders requires a large circuit area.
In an implementation of a multiplier where the design takes circuit area considerations into account, a single adder may be used under control of a state machine or software to perform a multiply operation in a sequence of iterations.
What is needed is a multiplier circuit and operating method that increases operating speed while retaining the compact circuit size of a single-multiplier iterative multiplication circuit.